/**
 * Written By: MinHo Kim (minho.kim.korea@gmail.com)
 * Copyright (C) 2011, MinHo Kim, Software Expert Program, KAIST University, Seoul, Korea.
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published 
 * by the Free Software Foundation; version 2 of the License.
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 * See the GNU General Public License for more details.
 */
package kaist.sep502.tsp.algorithm.search;

import kaist.sep502.tsp.algorithm.heuristic.Heuristic;
import kaist.sep502.tsp.model.CityPath;
import kaist.sep502.tsp.model.Problem;
import kaist.sep502.tsp.model.Solution;

/**
 * @author minho kim
 *
 */
public class GreedySearch extends SearchAlgorithm {

	/**
	 * @param problem
	 */
	public GreedySearch(Problem problem) {
		super(problem);
	}

	/* (non-Javadoc)
	 * @see kaist.sep502.tsp.algorithm.search.SearchAlgorithm#search()
	 */
	@Override
	public Solution search() {
		solution = new Solution("Greedy Search");
		solution.expandedNodeCount = 0;
		solution.startStopWatch();
		
		CityPath cityPath = new CityPath(problem, problem.departureCityNo);
		int departureCityNo = problem.departureCityNo;
		int currentCityNo = departureCityNo;
		Heuristic h = new Heuristic();
		
		try{
			do {
				solution.expandedNodeCount++;
				currentCityNo = problem.getClosestCityNo(currentCityNo, cityPath.tourHistory);
				
				if(currentCityNo == problem.goalCityNo){ // if it can't find the closest city, it means it travled all cities.
					currentCityNo = problem.goalCityNo;
				}
				
				h = heuristicAlgorithm.getHx(problem, cityPath, currentCityNo);
				cityPath.moveTo(problem, h.cityNo, h.hx);
			} while(currentCityNo != departureCityNo);
		} catch (Exception e){
			e.printStackTrace();
		}
		
		solution.setSuccess(true);
		solution.startStopWatch();
		solution.setGoalCityPath(cityPath);
		
		return solution;
	}
}
